#ifndef _HUFFMANTREE_H__
#define _HUFFMANTREE_H__

#include <queue>


template<class T>
struct HuffmanTreeNode
{
	HuffmanTreeNode<T>* _left;//左孩子
	HuffmanTreeNode<T>* _right;//右孩子
	T _value;//value值
	HuffmanTreeNode(const T&value)
		:_left(NULL)
		, _right(NULL)
		,_value(value)
	{}

};

template<class T>
class HuffmanTree
{
public:
	typedef HuffmanTreeNode<T> Node;
	HuffmanTree()//为什么要写无参构造？
		:_root(NULL)
	{}
	struct NodeCompare//仿函数的节点比较大小，其实是权值比较大小，内部重载了权值的+函数
	{
		bool operator()(const Node* l, const Node* r)//不需要修改，const修饰l，r对象调用_value内部函数
													//const对象不能调用非const函数,所以内部函数也要是const才行
		{
			return l->_value > r->_value;
		}
	};
	HuffmanTree(T* t, size_t n ,const T& invalid)//invalid代表插入的次数，次数大于1的插入
	{
		//构造哈夫曼树
		priority_queue<Node*, vector<Node*>, NodeCompare> minheap;//优先级队列构建哈夫曼树，默认是大堆，并且第一个参数传的是类型
																  //但是这里传的是节点指针，第三个参数是仿函数，
																  //原是比较类型的，现在是比较节点里的权值，所以要自己实现
		size_t i = 0;
		for (i = 0; i < n;++i)//插入数据
		{
			if (t[i] != invalid)//重载_count的！=函数
			{
				minheap.push(new Node(t[i]));
			}
		}
		while (minheap.size() > 1)//构建Huffman树
		{
			Node* left = minheap.top();
			minheap.pop();
			Node* right = minheap.top();
			minheap.pop();
			Node* parent = new Node(left->_value + right->_value);//其实是两个节点的CharInfo的权值相加，所以要重载+
			parent->_left = left;
			parent->_right = right;
			minheap.push(parent);

		}
		_root = minheap.top();//保存树的根；
	}
	~HuffmanTree()//释放树的空间
	{
		Destory(_root);
		_root = NULL;
	}
	void Destory(Node* root)
	{
		if (root->_left == NULL && root->_right == NULL)
			return;
		Destory(root->_left);
		Destory(root->_right);
		delete root;
	}
	Node* GetRoot()//返回树根
	{
		return _root;
	}
private:
	Node* _root;
	HuffmanTree(const HuffmanTree<T>& t);//防止外面调用拷贝函数和赋值拷贝函数而出错,因为是浅拷贝
	HuffmanTree<T>& operator=(const HuffmanTree<T>& t);
};



#endif//_HUFFMANTREE_H__
